#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-22 9:07 上午
# @Author  : yangdy
# @File    : 2020-07-22.剑指Offer11.旋转数组的最小数字
# @Software: PyCharmCE
from typing import List


class Solution:
    def minArray(self, numbers: List[int]) -> int:
        ans = 0
        ln = len(numbers)
        while ln > 1 and numbers[ln-1] == numbers[0]:
            numbers.pop()
            ln -= 1
        nums = [numbers[0]]
        for i in range(1, ln):
            if numbers[i] != numbers[i-1]:
                nums.append(numbers[i])
        ln = len(nums)
        l, r = 0, ln-1
        while l < r:
            h = (l+r)//2
            if nums[h] < nums[r]:
                r = h
            else:
                l = h + 1
            # elif nums[h] > nums[r]:
            #     l = h + 1
            # else:
            #     if nums[l] < nums[r]:
            #         r = h
            #     else:
            #         l = h + 1
        ans = nums[l]
        return ans


solve = Solution()

questions = [
    ([3, 4, 5, 1, 2],),
    ([2, 2, 2, 0, 1],),
    ([1, 3, 3],),
    ([3, 3, 1, 3],),
    ([10, 1, 10, 10, 10],),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.minArray(q[0]))

